//输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 
//
// 
//
// 参考以下这颗二叉搜索树： 
//
//      5
//    / \
//   2   6
//  / \
// 1   3 
//
// 示例 1： 
//
// 输入: [1,6,3,2,5]
//输出: false 
//
// 示例 2： 
//
// 输入: [1,3,2,6,5]
//输出: true 
//
// 
//
// 提示： 
//
// 
// 数组长度 <= 1000 
// 
// Related Topics 栈 树 二叉搜索树 递归 二叉树 单调栈 👍 419 👎 0

package com.cute.leetcode.editor.cn;

import java.util.Arrays;

public class ErChaSouSuoShuDeHouXuBianLiXuLieLcof {
    public static void main(String[] args) {
        Solution solution = new ErChaSouSuoShuDeHouXuBianLiXuLieLcof().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 不需要使用切割的方法，直接根据传入的数组进行判断就行了
         * 如果是一个顺序二叉树的后续遍历，那么根节点>左子树 && 根节点<右子树
         * start为当前子树的开始，end为当前子树的结束
         */
        public boolean verifyPostorder(int[] postorder) {
            return recur(postorder, 0, postorder.length-1);
        }
        public boolean recur(int[] postOrder, int start, int end){
            if (start >= end) return true;// 一个节点，直接返回true
            int p = start;
            while (postOrder[p] < postOrder[end]) p++;// 寻找右子树的第一个节点下标
            int m = p;// m即为右子树的开始
            while (postOrder[p] > postOrder[end]) p++;// 正常情况下p会直接到达当前的end处
            //必须当前情况，左子树和右子树同时满足才行
            return p == end && recur(postOrder, start, m-1) && recur(postOrder, m,end-1);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}